package main

type Data struct {
	lineSet   [9]int
	columnSet [9]int
	blockSet  [3][3]int
	spaces    [][2]int
	board     [][]byte
}

func solveSudoku(board [][]byte) {
	var lineSet, columnSet [9]int
	var blockSet [3][3]int
	var spaces [][2]int
	for i, line := range board {
		for j, pos := range line {
			if pos == '.' {
				spaces = append(spaces, [2]int{i, j})
			} else {
				digit := pos - '1'
				lineSet[i] ^= 1 << digit
				columnSet[j] ^= 1 << digit
				blockSet[i/3][j/3] ^= 1 << digit
			}
		}
	}
	data := &Data{
		lineSet:   lineSet,
		columnSet: columnSet,
		blockSet:  blockSet,
		spaces:    spaces,
		board:     board,
	}
	dfs(0, data)
}

func dfs(idx int, data *Data) bool {
	if idx == len(data.spaces) {
		return true
	}
	i, j := data.spaces[idx][0], data.spaces[idx][1]
	for digit := byte(0); digit < 9; digit++ {
		flag := 1 << digit
		inLine := data.lineSet[i]&flag > 0
		inColumn := data.columnSet[j]&flag > 0
		inBlock := data.blockSet[i/3][j/3]&flag > 0
		if !inLine && !inColumn && !inBlock {
			data.lineSet[i] ^= flag
			data.columnSet[j] ^= flag
			data.blockSet[i/3][j/3] ^= flag
			data.board[i][j] = digit + '1'
			if dfs(idx+1, data) {
				return true
			}
			// revert
			data.lineSet[i] ^= flag
			data.columnSet[j] ^= flag
			data.blockSet[i/3][j/3] ^= flag
		}
	}
	return false
}

func main() {
	board := [][]byte{
		{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
		{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
		{'.', '9', '8', '.', '.', '.', '.', '6', '.'},

		{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
		{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
		{'7', '.', '.', '.', '2', '.', '.', '.', '6'},

		{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
		{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
		{'.', '.', '.', '.', '8', '.', '.', '7', '9'},
	}
	solveSudoku(board)
	println(toStr(board))
}

func toStr(board [][]byte) string {
	str := ""
	for _, line := range board {
		for _, pos := range line {
			s := string([]byte{pos, ' '})
			str += s
		}
		str += "\n"
	}
	return str
}
